package 递归回溯;

import com.alibaba.fastjson.JSON;
import jvm.MyClassLoader;

import java.util.*;

public class No47全排列II {

    /**
     * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     * <p>
     * 示例 1：
     * 输入：nums = [1,1,2]
     * 输出：
     * [[1,1,2],
     * [1,2,1],
     * [2,1,1]]
     * 示例 2：
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     */

    List<List<Integer>> lists = new ArrayList<>();
    Set<List<Integer>> set = new HashSet<>();
    boolean[] flag;
    int count;

    public List<List<Integer>> permuteUnique(int[] nums) {
//        flag=new boolean[nums.length];
//        dg(new ArrayDeque<>(),nums);
//        return lists;
        this.flag = new boolean[nums.length];
        Arrays.sort(nums);
        this.dgGood(new ArrayDeque<>(), nums);
        return this.lists;
    }

    /**
     * 更优解法,去除set,使用Arrays.sort()对数组进行排序,相邻元素相同即可剪枝
     */
    private void dg(Deque<Integer> stack, int[] nums) {

        if (stack.size() == nums.length) {
            ArrayList<Integer> list = new ArrayList<>(stack);
            if (this.set.contains(list))
                return;
            this.set.add(list);
            this.lists.add(list);
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (this.flag[i])
                continue;
            stack.addLast(nums[i]);
            this.flag[i] = true;
            this.dg(stack, nums);
            stack.removeLast();
            this.flag[i] = false;
        }

    }

    private void dgGood(Deque<Integer> stack, int[] nums) {

        if (stack.size() == nums.length) {
            this.lists.add(new ArrayList<>(stack));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            //写flag[i-1]虽然容易理解,但是写!flag[i-1]更好
            //[因为dgGood调用完以后，!flag[i]，也就是说在下次循环开始，!flag[i-1]代表它已经被访问过了。
            //会立即剪枝,而flag[i-1]会在以后遍历中才会用到。]
            //上面那一句的基础是顺序遍历才有的性质,但是理解起来有点难度。
            if (this.flag[i] || (i > 0 && nums[i] == nums[i - 1] && this.flag[i - 1]))
                continue;
            this.count++;
            stack.addLast(nums[i]);
            this.flag[i] = true;
            this.dgGood(stack, nums);
            stack.removeLast();
            this.flag[i] = false;
        }
    }

    public static void main(String[] args) throws ClassNotFoundException {
        No47全排列II n = new No47全排列II();
        List<List<Integer>> lists = n.permuteUnique(new int[]{1, 1, 2, 4, 5, 5, 6, 2, 4});
        System.out.println(lists.size());
        System.out.println(JSON.toJSONString(lists));
        System.out.println("次数:" + n.count);
        ClassLoader classLoader = No47全排列II.class.getClassLoader();
        MyClassLoader classLoader1 = new MyClassLoader();
        Class<?> aClass = classLoader.loadClass("递归回溯.No46全排列");
        Class<?> aClass2 = classLoader1.loadClass("递归回溯.No46全排列");
        System.out.println(aClass.toString());
        System.out.println(aClass2.toString());
        System.out.println(aClass == aClass2);
    }

}
